import sys
import random
import population
import operator
from copy import deepcopy
class Crossover:

	def __init__(self, arity):
		self.arity = arity
	
	def __arrange_mates(self, parents):
		mates = []
		for i in range(0, len(parents), self.arity):
			mates.append(parents[i:i+self.arity])
	
		return deepcopy(mates)

	def one_point(self, parents, prob):
		"""
		One-point crossover
		
		Given two parents, chooses one cut-point, splits both parents at
		this point and then creates two children by exchanging the tails
		
		. Parameters:
			parents:	The list of parents selected for recombination
			prob:   	Recombination probability.
		
		. Return value:
			A population containing the new generation.
		"""
				
		# Reuses n_points crossover
		return self.n_points(parents, prob, 1)
	
	
	def one_point_crossover(self, probability, numPoints):
		return (lambda parents: self.one_point(parents, probability))


	def n_points(self, parents, prob, n):
		"""
		N-Points crossover
		
		Similar to one-point crossover, but with more that just one
		cut-point.
		
		. Parameters
			parents:	A tuple of two parents
			prob:		Recombination probability.
			n: 			Number of cut-points
		
		. Return value
			A population containing the new generation.
		"""
		
		def get_cut_points(n, count):
			"""
			Returns a list with n cut_points between 0 and count
			"""
			cut_points = []
			
			while len(cut_points) < n:
				new_point = random.randint(0, count)
				if cut_points.count(new_point) == 0:
					cut_points.append(new_point)
			
			cut_points.sort()			
			return [0] + cut_points + [count]
		
		def to_mask(cut_points, arity):
			"""
			Converts the cut points list to an equivalent list that can be used by uniform crossover
			
			e.g. if
			
			> cut_points = [0, 3, 5, 7]
			
			and
			
			> arity = 2
			
			then, the mask will be
			
			> mask = [0, 0, 0, 1, 1, 0, 0]
			
			mask[i] = 0 means that the value for the ith bit should be taken from the first parent, while
			mask[i] = 1 means that the value for the ith bit should be taken from the second parent.
			"""
			return reduce(operator.add, [[(i-1) % arity] * (cut_points[i] - cut_points[i-1]) for i in range(1, len(cut_points))])

		mask = [[to_mask(get_cut_points(n, len(var)), self.arity) for var in parents[0]] for i in range(len(parents) / self.arity)]
		
		# reuses uniform crossover
		return self.uniform(parents, prob, mask)

	def n_points_crossover(self, prob, n):
		return (lambda parents: self.n_points(parents, prob, n))


	def u_scan(mates):
		"""
		Uniform scanning for multi-parent recombination
		
		Generates a random mask, i.e., each parent has equal chances of donating the ith gene
		"""
		return [[random.randint(0, len(mates) - 1) for index in range(len(var))] for var in mates[0]]
	
	def ob_scan(mates):
		"""
		Ocurrence based scanning for multi-parent recombination
		"""
		def most_frequent(values):			
			"""
			Returns the index of one of the elements with the most frequent entry
			In case of a tie, returns the index of the first element, 0.
			
			values must contain 0's and 1's only.
			"""
			sum = reduce(operator.add, values)
			if sum > len(mates) / 2.0:
				return values.index(1)
			elif sum < len(mates) / 2.0:
				return values.index(0)
			else:
				return 0
					
		return [[most_frequent([mate[v][j] for mate in mates]) for j in range(len(mates[0][v]))] for v in range(len(mates[0]))]

	def fb_scan(mates):
		"""
		Fitness based scanning for multi-parent recombination
		"""
		def corresponding_mate(mates, number):
			"""
			Given a random number and a set of parents, returns the index of the parent
			corresponding to the number. Parents are weighted according to their fitness,
			in a way very similar to roulette selection.
			
			For instance, if the fitness of the parents are 250, 500 and 250 (total fitness = 1000) 
			and the random number is between 0 and 250/1000 = 1/4, the first parent will be choosen. 
			If the number is between 1/4 and 3/4, the second parent will be choosen. Otherwise,
			the third parent will be selected.
			"""
			fitness_sum = reduce(operator.add, [mate.get_fitness() for mate in mates])			
			total_fitness = 0
			for mate, index in zip(mates, range(len(mates))):
				total_fitness += mate.get_fitness()
				if (number <= total_fitness / fitness_sum):
					return index
		
		return [[corresponding_mate(mates, random.random()) for j in range(len(mates[0][v]))] for v in range(len(mates[0]))]
		

	def uniform(self, parents, prob, mask=None, scanner=u_scan):
		"""
		Uniform crossover
		
		Chooses each new gene from some parent choosen randomly.
		
		. Parameters
			parents:	    The list of parents choosen by the selection
                            mechanism to reproduce.
			prob:			Recombination probability.
			mask:			mask[i] contains the index of the parent from where the ith bit is to be taken
							Note that mask can be None. In that case it will be generated internally.
							
							for instance, if
							
							 > parent[0]   = [1, 2, 3]
							 > parent[1]   = [4, 5, 6] 
							 > parent[2]   = [7, 8, 9] 
							
							 and 
							
							 > mask = [0, 1, 2] 
							
							 then
							
							 > children[0] = [1, 5, 9]
							 > childnre[1] = [4, 8, 3]
							 > children[2] = [7, 2, 6]
		
		. Return value
			A population containing the new generation.
		"""
        
		def uniform_helper(mates, prob, mask):
			"""
			Performs uniform crossover for a single reprodution between two (or more) parents
			"""
			if random.random() < prob:					
				children = [population.Individual(individual) for individual in mates]
				for child in children:
					child.remove_cromo();
					
				arity = len(mates)

				# If mates = [[[1, 5], [2, 6]], [[3, 7], [4, 8]]],
				# the zip() will return [([1, 5], [3, 7]), ([2, 6], [4, 8])]
				# Got it?
				for genes, var_mask in zip(zip(*[[gene[:] for gene in parent] for parent in mates]), mask):
					k = 0
					# Uses the mask to generate the new cromossomes
					for new_cromo in [[genes[(var_mask[j] + i) % arity][j] for j in range(len(var_mask))] for i in range(len(genes))]:
						children[k].genes.append(new_cromo)	
						k += 1	

				return children
			else:
				return deepcopy(mates)
		
			
		
		children = population.Population("Parameter Copy", pop=parents)
		
		all_mates = self.__arrange_mates(parents)
		
		# Generate mask using an uniform random generator by default
		# i.e., each parents has equal chances to donate the ith bit.
		if mask == None:
			mask = [scanner(mates) for mates in all_mates]
				
		for mates, pair_mask in zip(all_mates, mask):		
			for child in uniform_helper(mates, prob, pair_mask):
				children.add_individual(child)
				
		return children


	def uniform_crossover(self, prob, mask=None, scanner=u_scan):
		return (lambda parents: self.uniform(parents, prob, mask, scanner))


#	def whole_arithmetic(self, parents, prob, weighter):
#		"""
#		Whole arithmetic recombination
#		Children are the weighted average of both parents
#		
#		. Parameters
#			parents:	A tuple of two parents
#			prob:		Recombination probability.
#			weight:	(see page 51)
#		
#		. Return value
#			Returns a tuple with the two children.
#		"""
#
# Se genes = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# pesos = [0.1, 0.4, 0.5]
# [[reduce(operator.add, [k * pesos[(j+z)%3] for k,j in zip(i, range(len(i)))]) for i in zip(*genes)] for z in range(len(genes))]
# = [[5.2, 6.2, 7.2], [3.1, 4.1, 5.1], [3.7, 4.7, 5.7]]
#
# Depois e converter de float para binario e vice-versa
#        
#		def whole_arithmetic_helper(mates, prob, weights):
#			if random() < prob:
#				children = [population.Individual(individual) for individual in mates]
#				for child in children:
#					child.remove_cromo();
#					
#				# If mates = [[[1, 5], [2, 6]], [[3, 7], [4, 8]]],
#				# the zip() will return [([1, 5], [3, 7]), ([2, 6], [4, 8])]
#				# Got it?
#				for genes, var_mask in zip(zip(*[[gene[:] for gene in parent] for parent in mates]), mask):
#					k = 0
#			
#				return mates
#			
#		for mates in self.__arrange_mates(parents):		
#			for child in uniform_helper(mates, prob, weighter(mates)):
#				children.add_individual(child)
#				
#		return children
#	
#	def whole_arithmetic_crossover(self, prob, numPoints, weight):
#		return (lambda parents: self.whole_arithmetic(parents, prob, weight))

